327C - Magic Five - CodeForces Solution

#include<stdio.h>
#include<math.h>
#include<string.h>
#define ll long long int
ll ans=0;

ll po(ll x, ll y, ll ii){
	ll k, i, j; k=1;
	while(y>0){
		if(y%2==1){
			k=(k*x)%ii;
		} y=y/2; x=(x*x)%ii;
	} return k;
}

int main(){
	ll n, i, k, x, y, p, q, j, ii, jj, t, a[200010];
	char s[200010]; ii=1e9+7;
	scanf("%s", s); n=strlen(s);
	scanf("%lld", &k); y=1;
	for(i=0; i<n; i++){
		if(s[i]=='0' || s[i]=='5'){
			x=po(2, i+n*k, ii);
			p=po(2, n, ii);
			p=po(p-1, ii-2, ii);
			q=(x-y)%ii; q=(q*p)%ii; if(q<0) q+=ii;
			ans=(ans+q)%ii;
		} y=(y*2)%ii;
	}
	printf("%lld\n", ans);
	return 0;
}